package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 排序算法的稳定性测试
 * 
 * @author 付大石
 */

public class Main {

    public static void main(String[] args) {

        Task t1 = new Task("t1", 1000);
        Task t2 = new Task("t2", 500);
        Task t3 = new Task("t3", 1500);
        Task t4 = new Task("t4", 1000);
        Task t5 = new Task("t5", 1200);
        Task t6 = new Task("t6", 1900);
        SPT spt = new SPT(new Comparator<Task>() { // 最短处理时间优先

            @Override
            public int compare(Task t1, Task t2) {
                return (int) (t2.getTime() - t1.getTime());
            }
        });
        spt.insert(t1);
        spt.insert(t2);
        spt.insert(t3);
        spt.insert(t4);
        spt.insert(t5);
        spt.insert(t6);
        while (!spt.isEmpty()) {
            System.out.println(spt.optimal());
        }
    }

}

/**
 * 根据{@code comp}指定的优先原则打印调度报告
 * 
 * @author 付大石
 */
class SPT {

    private static final int CAPACITY = 20;
    private Task[] taskPQ; // 元素是Task对象实例的优先队列
    private int size;
    private Comparator<Task> comp;

    public SPT(Comparator<Task> comp) {
        taskPQ = new Task[CAPACITY + 1];
        this.comp = comp;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void insert(Task task) {

        if (size >= CAPACITY) {
            throw new RuntimeException("优先队列已满");
        }
        taskPQ[++size] = task;
        swim(size);
    }

    /**
     * 从优先队列中删除并获取最优的一个Task对象
     * 
     * @return
     */
    public Task optimal() {

        Task optimal = taskPQ[1];
        swap(1, size--);
        taskPQ[size + 1] = null; // 对象游离
        sink(1);
        return optimal;
    }

    private void swap(int i, int j) {

        Task temp = taskPQ[i];
        taskPQ[i] = taskPQ[j];
        taskPQ[j] = temp;
    }

    private void sink(int k) {

        Task target = taskPQ[k];
        while (2 * k <= size) {
            int i = 2 * k;
            if (i + 1 <= size && comp.compare(taskPQ[i], taskPQ[i + 1]) < 0) { // 找出优先级较大的一个元素
                i++;
            }
            if (comp.compare(target, taskPQ[i]) >= 0) {
                break;
            }
            taskPQ[k] = taskPQ[i];
            k = i;
        }
        taskPQ[k] = target;
    }

    /**
     * 上浮
     * 
     * @param k
     */
    private void swim(int k) {

        Task target = taskPQ[k];
        while (k > 1 && comp.compare(target, taskPQ[k / 2]) > 0) {
            taskPQ[k] = taskPQ[k / 2];
            k = k / 2;
        }
        taskPQ[k] = target;
    }
}

class Task {

    private String name;
    private long time;

    public Task() {

    }

    public Task(String name, long time) {
        this.name = name;
        this.time = time;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public long getTime() {
        return time;
    }

    public void setTime(long time) {
        this.time = time;
    }

    @Override
    public String toString() {
        return "Task [name=" + name + ", time=" + time + "]";
    }
}